\section{Introduction}
\subsection{Problem Description}
The problem of the minimum triangulation is defined as follows: Given a set of point $P \subseteq \mathbb{R}^2$ and a weight function $w: T(P) \mapsto \mathbb{R}$, where $T(P)$ is denoted to a valid triangulation of $P$, find $T(P)$ which is minimal in relation to the weight function. Some weight functions, like those to maximize the minimum angle of all triangles of the triangulation which is also known as Delaunay triangulation, are well known and studied and can be solved by several algorithms in polynomial time. On the other hand, there are weight functions that result in NP-hard problems. An example of this is to minimize the length of all edges over all triangles which is generally called minimum weight triangulation (cmp. \cite{Mulzer2008}).

Since the minimum weight triangulation is NP-hard, there is no polynomial time algorithm to compute this kind of triangulation. However, the LMT algorithm is a heuristic approach. This algorithm computes the LMT-skeleton, which is a subgraph of the minimal weight triangulation, in polynomial time. With a high probability this subgraph is connected and the missing parts consist of simple polygons only. These can be deterministically triangulated in polynomial time. One advantage of the LMT-heuristic is that it does not rely on the weight function used, therefore any possible and reasonable weight function can be used.

\subsection{Goals}
The goal of this project is to develop an application with a graphical user interface for triangulating arbitrary point sets and displaying these triangulations. The LMT-heuristic will be used for computing the triangulations. Special focus will be on possible speed enhancements by using efficient data structures, since a na\"ive implementation of this algorithm has an asymptotic running time of $O(n^6)$ where $n$ is the number of points that will be triangulated. This can be improved up to $O(n^2)$ by taking care of some additional information as shown in section \ref{sec:optimization}.

Other design issues are an easy way to implement additional weight functions because the program will be used to observe the resulting triangulations of different weight functions. It can be used to determine possible weight function also resulting in NP-hard problems and find point sets as basis for a proof of the NP-hardness of these kind of triangulations. Therefore, additional weight functions had to be implemented within the scope of this project.

To end up with a re-usable codebase, the logic will be separated from the GUI, making an extraction of the implemented algorithms into an external library easier. The goal is to make the implemented algorithms usable by other application or even as single tool which outputs the triangulation in a desired format which can be used for further processing by other applications. Since the lack of Java-based algorithms and libraries for computational geometry compared to languages like C++ or Python, the Java 1.6 programming language will be used for this project.

  
